1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static void solve () { int x = io.nextInt(), k = io.nextInt(); while (sum(x) % k != 0 ) { x++; } io.println(x); } private static int sum (int x) { int res = 0 ; while (x != 0 ) { res += x % 10 ; x /= 10 ; } return res; }
好难啊,做得很慢。对于每个 \(i\),如果它是满足条件的,那么 \([n-i,n-1]\) 需要全为 \(0\),它的最少操作次数为 \([n-i,n-1]\) 中所有值为 \(1\) 的下标和,减去 \([0,n-i-1]\) 中最近的值为 \(0\) 的对应个数的下标和。我们可以使用双指针 \(O(n)\) 的计算所有 \(i\),具体见代码。指针 \(j\) 枚举每个下标,同时求出后缀的下标和,指针 \(i\) 指向指针 \(j\) 需要的最远的 \(0\) 的下标位置,同时求出后缀值为 \(0\) 的下标和,它们的差值就是 \(j\) 的最少操作次数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public static void solve () { int n = io.nextInt(); String s = io.next(); long sum = 0L ; int i, j, cnt = 0 ; for (i = n - 1 , j = n - 1 ; i >= 0 ; j--) { cnt++; sum += j; for (; i >= 0 && cnt > 0 ; i--) { if (s.charAt(i) == '0' ) { cnt--; sum -= i; } } io.print(cnt > 0 ? "-1 " : sum + " " ); } io.println("-1 " .repeat(j + 1 )); }
发现一个超级简单的写法,基本思路就是从低到高放置 \(0\),操作次数即为 \(0\) 的移动次数,废话不多说,代码很好懂。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static void solve () { int n = io.nextInt(); char [] s = io.next().toCharArray(); long ans = 0L ; int l = n - 1 , r = n - 1 ; for (; l >= 0 ; l--) { if (s[l] == '0' ) { ans += r - l; r--; io.print(ans + " " ); } } io.println("-1 " .repeat(r + 1 )); }
最小值一定在位置 \(1\) 或位置 \(m\),我们可以考虑处理区间不包含 \(1\) 和不包含 \(m\) 两种情况下,能够得到的最大值,根据简单的推导可以知道问题是等价的。如何计算最大值,根据题解所说似乎是扫描线算法,使用 \((l,1)\) 表示进入某个区间,\((r,-1)\) 表示离开某个区间,注意初始时我们将每个左端点减 \(1\),表示从区间 \(0\) 开始算,\((l,r)\) 是左闭右开区间,所以 \(r\) 表示离开某个区间,然后每当处理完某个端点就更新答案。(其实也可以使用差分哈希表进行区间求和)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 public static void solve () { int n = io.nextInt(), m = io.nextInt(); int [] l = new int [n]; int [] r = new int [n]; for (int i = 0 ; i < n; i++) { l[i] = io.nextInt() - 1 ; r[i] = io.nextInt(); } List<int []> list = new ArrayList <>(); for (int i = 0 ; i < n; i++) { if (l[i] != 0 ) { list.add(new int []{l[i], 1 }); list.add(new int []{r[i], -1 }); } } list.sort((a, b) -> a[0 ] - b[0 ]); int ans = sweep(list); list.clear(); for (int i = 0 ; i < n; i++) { if (r[i] != m) { list.add(new int []{l[i], 1 }); list.add(new int []{r[i], -1 }); } } list.sort((a, b) -> a[0 ] - b[0 ]); ans = Math.max(ans, sweep(list)); io.println(ans); } private static int sweep (List<int []> list) { int res = 0 , cnt = 0 , lst = 0 ; for (int [] t : list) { if (t[0 ] > lst) { res = Math.max(res, cnt); } cnt += t[1 ]; lst = t[0 ]; } return res; }
一对数 \(x,y\) 不能同时被数组中的数整除,即 \(\gcd(x,y)\) 不能被数组中的数整除。我们首先可以计算出数组中有多少对数它们的 \(\gcd=1,2,3\dots,n\),然后排除掉能够被数组中的数整除的 \(\gcd\),剩下的 \(\gcd\) 对应的对数之和就是答案。第一步可以使用动态规划求解,转移方程如下:
$$
sum = cnt[i]+cnt[2\times i]+\cdots+cnt[k\times i] \\
dp[i]= \frac{sum\times (sum-1)}{2}-(dp[2\times i]+dp[3\times i]+\cdots+dp[k\times i])
$$
第二步切记不能枚举数组中的数来排除,这样在所有值都为 \(1\) 的样例下时间复杂度会达到 \(O(n^{2})\),除非将数组去重,或者像下面代码一样枚举。最后计算答案即可。本题的另一种解法是 GCD 卷积,暂时不学。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public static void solve () { int n = io.nextInt(); int [] a = new int [n]; int [] cnt = new int [n + 1 ]; for (int i = 0 ; i < n; i++) { a[i] = io.nextInt(); cnt[a[i]]++; } long [] dp = new long [n + 1 ]; for (int i = n; i > 0 ; i--) { long tot = 0L ; for (int j = i; j <= n; j += i) { tot += cnt[j]; dp[i] -= dp[j]; } dp[i] += tot * (tot - 1 ) / 2 ; } for (int i = 1 ; i <= n; i++) { if (cnt[i] != 0 ) { for (int j = i; j <= n; j += i) { dp[j] = 0 ; } } } long ans = 0L ; for (int i = 1 ; i <= n; i++) { ans += dp[i]; } io.println(ans); }